package interview.treetraversal;

import interview.common.BinaryTreeNode;
import java.util.Stack;

public class TreeTraversal {
	public void inOrderRecursive(BinaryTreeNode root) {
		if(root == null) {
			return;
		}
		
		inOrderRecursive(root.getLeft());
		System.out.print(root.getData() + " ");
		inOrderRecursive(root.getRight());
	}
	
	public void preOrderIterative(BinaryTreeNode root) {
		Stack<BinaryTreeNode> sTreeNode = new Stack<BinaryTreeNode>();
		sTreeNode.push(root);
		while(!sTreeNode.empty()) {
			BinaryTreeNode current = sTreeNode.pop();
			System.out.println(current.getData());
			if(current.getRight() != null) {
				sTreeNode.push(current.getRight());
			}
			if(current.getLeft() != null) {
				sTreeNode.push(current.getLeft());
			}
		}
	}
	
	public void inOrderIterative(BinaryTreeNode root) {
		Stack<BinaryTreeNode> sTreeNode = new Stack<BinaryTreeNode>();
		
		BinaryTreeNode current = root;
		while(!sTreeNode.empty() || current != null) {
			if(current != null) {
				sTreeNode.push(current);
				current = current.getLeft();
			} else {
				current = sTreeNode.pop();
				System.out.print(current.getData() + " ");
				current = current.getRight();
			}
		}
	}
	
	public void postOrderIterative2(BinaryTreeNode root) {
		Stack<BinaryTreeNode> sTreeNode = new Stack<BinaryTreeNode>();
		Stack<BinaryTreeNode> sOutput = new Stack<BinaryTreeNode>();
		
		sTreeNode.push(root);
		while(!sTreeNode.empty()) {
			BinaryTreeNode current = sTreeNode.pop();
			sOutput.push(current);
			if(current.getLeft() != null) {
				sTreeNode.push(current.getLeft());
			}
			if(current.getRight() != null) {
				sTreeNode.push(current.getRight());
			}
		}
		
		while(!sOutput.empty()) {
			System.out.print(sOutput.pop().getData() + " ");
		}
		System.out.println();
	}
	
	public void postOrderIterative(BinaryTreeNode root) {
		Stack<BinaryTreeNode> sTreeNode = new Stack<BinaryTreeNode>();
		sTreeNode.push(root);
		BinaryTreeNode current = null;
		while(!sTreeNode.empty()) {
			current = sTreeNode.peek();
			if(current.getRight() != null) {
				if(current.getRight().isVisited()) {
					current = sTreeNode.pop();
					System.out.println(current.getData());
					current.setVisited(true);
				} else {
					sTreeNode.push(current.getRight());
					if (current.getLeft() != null) {
						if(!current.getLeft().isVisited()) {
							sTreeNode.push(current.getLeft());
						}
					}
				}
			} else if (current.getLeft() != null) {
				if(current.getLeft().isVisited()) {
					current = sTreeNode.pop();
					System.out.println(current.getData());
					current.setVisited(true);
				} else {
					sTreeNode.push(current.getLeft());
				}
			}
		}
	}
}
